package com.justnow;

import java.util.Arrays;

public class Solution1 {

    //我的方法，双指针，定位左边和右边第一个逆序的位置，最后相减获取长度.会存在一些问题，所以，这个方法还是不太行
    public int findUnsortedSubarray(int[] nums) {
        int result, head = 0, tail = nums.length - 1;
        if (nums[head] > nums[tail]) {
            result = nums.length;
            return result;
        }
        int start = 0, end = 0;
        boolean flaghead = false;
        boolean flagtail = false;
        while (head < tail) {
            if (nums[head] <= nums[head+1] && nums[head] < nums[tail])  {
                //加上=防止出现[1, 1, 2, 3, 3]的问题，即相等了去跳到else语句块
                head++;
            } else {
                start = head;
                flaghead = true;
            }
            if (nums[tail] >= nums[tail-1]) {
                tail--;
            } else {
                end = tail;
                flagtail = true;
            }
            if (flaghead && flagtail) {
                break;
            }
        }

        //排除 数组有序！
        if (end == start) {
            return 0;
        }
        return end - start + 1;
    }

    //方法二，排序
    public int findUnsortedSubarray2(int[] nums) {
        //时间复杂度为O(nlogn)
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for (int i = 0; i < snums.length; i++) {
            if (snums[i] != nums[i]) {
                //start为从左边数第一个不想等的数字
                start = Math.min(start, i);
                //end为右边数第一个不想等的数字。
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }
    public static void main(String[] args) {
        int[] nums = {2, 6, 4, 8, 10, 9, 15};
        Solution1 solution1 = new Solution1();
        int unsortedSubarray = solution1.findUnsortedSubarray(nums);
        System.out.println(unsortedSubarray);
    }
}
